1. Field of the Invention
The invention pertains to the field of mathematical analysis and modeling. More particularly, the invention pertains to a dynamical method for obtaining a global optimal solution of general nonlinear programming problems.
2. Description of Related Art
A large variety of the quantitative decision issues arising in the sciences, engineering, and economics can be perceived and modeled as constrained nonlinear optimization problems. According to this generic description, the best decision, often expressed by a real vector, is sought in the search space which satisfies all stated feasibility constraints and minimizes (or maximizes) the value of an objective function. The vector, if it exists, is termed the “global optimal solution.” In general, there are solutions that are locally optimal (a local optimal solution is optimal in a local region of the search space) but not globally optimal.
In general, the search space of a constrained nonlinear optimization problem contains a number of local optimal solutions. Typically, the number of local optimal solutions is unknown and it can be quite large. Furthermore, the values of an objective function at local optimal solutions and at the global optimal solution may differ significantly. The great majority of existing nonlinear optimization techniques usually come up with local optimal solutions but not the global optimal one.
The task of finding the global optimal solution of constrained nonlinear optimization problems is important for a very broad range of applications in the design, operation, and planning problems arising in various engineering disciplines and the sciences. Engineering application areas include, for example, structural optimization, engineering design, VLSI chip design and database problems, image processing, computational chemistry, molecular biology, nuclear and mechanical design, chemical engineering design and control, optimal power flow in electric networks, economies of scale, fixed charges, allocation and location problems, and quadratic assignment, as well as numerous other applications.
The problem of finding the global optimal solution, termed the Global Optimization (GO) problem is very difficult and challenging. From the computational complexity point of view, the task of finding the global optimal solution of constrained nonlinear optimization problems belongs to the class of NP-hard problems. This implies that the computational time required to solve the problem is expected to grow exponentially as the input size of the problem increases.
Existing methods proposed for solving the GO problem can be categorized into three classes: deterministic methods, stochastic methods, and hybrid methods. Deterministic methods typically provide mathematical guarantees for convergence to an approximate global minimum in finite steps for optimization problems involving certain mathematical structures. This class of methods includes the branch and bound methods, cutting planes, decomposition-based approaches, covering methods, interval methods, homotopy methods, and generalized gradient methods. On the other hand, stochastic methods require sampling the objective functions and perhaps computing their derivatives to find the global optimal solution. They are applicable to a wide range of GO problems; however, the required number of samples necessary to arrive at the global optimal solution is often prohibitive for high-dimension problems. The class of stochastic methods is characterized by a slow convergence and a lack of accuracy when an exact global optimal solution is required. Random search methods, genetic algorithms, simulated annealing, clustering methods, and Bayesian methods all belong to the class of stochastic methods. Hybrid methods for GO problems is a recently proposed class; this class of methods usually, if not always, combines one stochastic method, for example, the genetic algorithms, with one classical ‘hill-climbing’ method, such as the Quasi-Newton method. The idea of combining two different methods into one in order to attempt to merge their advantages and to reduce their disadvantages is well known. The question associated with this combination is what methods to merge and how to merge them. This class of hybrid methods suffers from a slow convergence, inherited from the stochastic method, but it improves the problem of accuracy with the help of a ‘hill-climbing’ method.
The only reliable way to find the global optimal solution of a nonlinear optimization problem is to first find all the local optimal solutions and then find, from them, the global optimal solution. In the present invention, we develop a new systematic methodology, which is deterministic in nature, to find all the local optimal solutions of both unconstrained and constrained nonlinear optimization problems. Two classes of global optimization methodology are developed in this invention:                a dynamical trajectory-based methodology for unconstrained nonlinear programming problems; and        a dynamical trajectory-based methodology for constrained nonlinear programming problems.        
For unconstrained nonlinear optimization problems, one distinguishing feature of the new methodology is that it systematically finds all the local optimal solutions. For constrained nonlinear optimization problems, one distinguishing feature of the new methodology of the present invention is that it systematically finds all the local optimal solutions of constrained nonlinear optimization problems whose feasible regions can be disconnected. Our developed methodology consists of two distinct phases: Phase I systematically locates each connected feasible region of the entire feasible region. Phase II then finds all the local optimal solutions lying in each feasible region obtained in Phase I.
In the present invention, methods are developed for the following two important issues in the search for the global optimal solution:
(i) how to effectively move (escape) from a local optimal solution and move on toward another local optimal solution; and
(ii) how to avoid revisiting local optimal solutions which are already known.
In the past, significant efforts have been directed towards attempting to address this issue, but without much success. Issue (i) is difficult to solve and both the class of deterministic methods and the class of stochastic methods all encounter this difficulty. Issue (ii), related to computational efficiency during search, is also difficult to solve and, again, both the class of deterministic methods and the class of stochastic methods encounter this difficulty. In the present invention, effective methods to overcome these issues are developed and incorporated into the dynamical trajectory-based methodology.
Our previous work related to unconstrained global optimization problems is described in H. D. Chiang, Chia-Chi Chu, A Systematic Search Method for Obtaining Multiple Local Optimal Solutions of Nonlinear Programming Problems, IEEE Trans. Circuits and Systems, vol. 43, pp. 99-109, 1996, the complete disclosure of which is hereby incorporated herein by reference. This work focused on the idea of constructing a particular nonlinear dynamical system and on the development of conceptual methods that are rich in theory, but are difficult, if not impossible, to implement numerically for practical applications. This work was extended to constrained global optimization problems in Jaewook Lee, Path-following methods for global optimization, Ph.D. dissertation, Cornell Univ., NY, 1999, the complete disclosure of which is hereby incorporated herein by reference. Among other things, this publication presents construction of two particular nonlinear dynamical systems for performing a two-phase optimization procedure, which is again rich in theory but difficult, if not impossible, to implement numerically for practical applications. The idea of computing exit points of a class of non-linear systems in U.S. Pat. No. 5,483,462, On-line Method for Determining Power System Transient Stability, issued to Hsiao-Dong Chiang on Jan. 9, 1996, the complete disclosure of which is hereby incorporated herein by reference.
This invention differs from the prior art in the following aspects (as well as others):    (1) this invention develops a class of nonlinear dynamical systems (see conditions (C1) and (C2) for unconstrained optimization problems and conditions (C1-1), (C1-2), (C2-1) and (C2-2) for constrained optimization problems) and shows that their system trajectories can be exploited to develop numerical methods for finding a complete set of local optimal solutions and the global optimal solution    (2) the particular nonlinear dynamical systems in the aforementioned publications all belong to the class of nonlinear dynamical systems developed in this invention    (3) this invention develops a dynamical trajectory-based method which can incorporate any existing local optimizer (i.e., a method for finding a local optimal solution) into it, hence, this invention can be applied to guide any existing computer package to find a complete set of local optimal solutions and the global optimal solution    (4) this invention can be programmed to interface with any existing computer package without the need to modify the ‘environment’ of the existing computer package (which include the graphical user interface data base) to find a complete set of local optimal solutions and the global optimal solution, and, in particular, this invention imposes no new learning curve for the user in the combined computer package    5) this invention develops a numerical method, termed dynamical decomposition point search method, for guiding the search process to escape from trapping at a local optimal solution in a deterministic manner    6) this invention extends a previous patented method to develop a numerical method, termed a numerical method for computing the exit point, which is incorporated into the dynamical decomposition point search method    7) this invention develops a numerical method, termed an improved method for computing the exit point, which is incorporated into the dynamical decomposition point search method    8) this invention develops a numerical method, termed a numerical method for computing the minimum distance point (MDP), which is incorporated into the dynamical decomposition point search method    9) this invention develops a numerical method, termed an improved method for computing the minimum distance point (MDP), which is incorporated into the dynamical decomposition point search method    10) this invention develops a hybrid search method, which is composed of a trajectory-based method and an effective local optimization method for finding local optimal solutions. The hybrid method shares the reliability and accuracy of the former method and the accuracy and computational speed of the latter    11) this invention develops a method for anti-revisit of local optimal solutions to avoid searching regions which contain previously found local optimal solutions. The invention also develops a DDP-based numerical method, which, in combination with the DDP search method, performs a procedure that searches from a local optimal solution to find another local optimal solution in a deterministic manner    12) this invention develops a dynamical trajectory-based method, which can incorporate any existing local optimizer (i.e., a method for finding a local optimal solution). Hence, this invention can be applied to guide any existing computer package to find a complete set of local optimal solutions and the global optimal solution. The invention can be programmed to interface with any existing computer package without the need to modify the ‘environment’ of the existing computer package (which includes the graphical user interface data base) to find a complete set of local optimal solutions and the global optimal solution. In particular, this invention imposes no new learning curve for the user in the combined computer package
The theoretical basis of these methods is described as follows.
We treat the problem of how to escape from a local optimal solution and to move on toward another local optimal solution as the problem of how to escape from the stability region of the corresponding (asymptotically) stable equilibrium point (s.e.p.) of a nonlinear dynamical system satisfying certain conditions and enter into the stability region of another corresponding s.e.p. of the nonlinear dynamical system. There are several ways to construct nonlinear dynamical system satisfying the required conditions. The present invention presents guidelines for constructing such nonlinear dynamical systems.
One common problem which degrades the performance of many existing methods searching for the global optimal solution is the re-visitation of the same local optimal solutions several times; this wastes computing resources without gaining new information regarding the location of the global optimal solution. From the computational viewpoint, it is important to avoid revisiting the same local optimal solution in order to maintain a level of efficiency. To address issue (ii), we develop in this invention an anti-revisiting search method for both unconstrained and constrained optimization problems. The theoretical basis of the anti-revisiting search method rests on the dynamical decomposition points developed in this invention.
The present invention develops a method for anti-revisit of local optimal solutions to avoid searching regions which contain previously found local optimal solutions. The invention also develops a DDP-based numerical method, which, in combination with the DDP search method, performs a procedure that searches from a local optimal solution to find another local optimal solution in a deterministic manner.
From a practical viewpoint, the dynamical trajectory-based methodology developed in this invention requires integrating a set of ordinary differential equations (ODE). It was thought by many that ODE solvers are too extensive to be of general use compared with, for example, a conventional Newton-type method. However, their performance is significantly affected by the choice of integration method and the way in which the step size is controlled. When suitably implemented, these methods deserve a place in the mainstream of optimization algorithm development. See, for example, A. A. Brown and M. C. Bartholomew-Biggs, Some effective methods for unconstrained optimization based on the solution of systems of ordinary differential equations, Journal of Optimization Theory and Applications, vol. 62, pp. 211-224, 1989, the complete disclosure of which is hereby incorporated herein by reference.
The present invention develops a dynamical trajectory-based method, which can incorporate any existing local optimizer (i.e., a method for finding a local optimal solution). Hence, this invention can be applied to guide any existing computer package to find a complete set of local optimal solutions and the global optimal solution. The invention can be programmed to interface with any existing computer package without the need to modify the ‘environment’ of the existing computer package (which includes the graphical user interface data base) to find a complete set of local optimal solutions and the global optimal solution. In particular, this invention imposes no new learning curve for the user in the combined computer package.